package com.lagou;

/**
 * 给定一个链表，判断链表中是否有环。存在环返回 true ，否则返回 false，约束时间复杂度为 O(n)。
 *
 * @author wanggege
 */
public class Demo02 {

    public static boolean isRing(Node head) {

        if (head == null) return false;
        //定义快慢指针
        Node slow = head; //慢指针
        Node fast = head.next; //快指针

        while (fast != null && fast.next != null) {
            //有环
            if (slow == fast) {
                return true;
            }
            fast = fast.next.next;
            // 快指针步长为2
            slow = slow.next;
            //慢指针步长为1
        }
        return false;


    }

    public static void main(String[] args) {


        Node n1 = new Node(1, "张飞");
        Node n2 = new Node(2, "关羽");
        Node n3 = new Node(3, "赵云");
        Node n4 = new Node(4, "黄忠");
        Node n5 = new Node(5, "马超");

        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = null;

        System.out.println(isRing(n1));
    }


}
